Replacement methods apply particularly to data processing systems comprising a hierarchized memory and/or a virtual memory, that are presently in use in most computers. They allow the control of paged memory (central memory), cache memory, and address translators (Translation Look-aside Buffers TLB) of such computers.
A hierarchized memory system comprises a processor and a large capacity background store. In view of the latter's inherently low speed it is necessary to interpose one or more intermediate memory levels between the processor and the background memory. Generally, the closer the memory level in question is to the processor, the faster its operating speed but the lower its storage capacity. Because of this, each memory level contains only a part of the information which is contained by the level which immediately follows it on the mass memory side. Therefore, if the processor supplies an address that is not present in a particular memory level, the memory management system must search for the information in an upstream level and load it into the level originally addressed. If, however, the latter level is full, the memory management system according to a predefined replacement algorithm must delete the information present in one of the memory elements to allocate its space to the new information. Generally, the information that is most useful to the processor must be stored as closely as possible thereto, because fetching information that is further away is a time-consuming operation.
A similar replacement problem arises in virtual memory systems. In order to avoid translating the virtual page number into a physical page number at each access, a few "virtual page, physical page" pairs which have been used are retained in a small buffer register called an address translator (Translation Look-aside Buffers TLB). When a new page is addressed, it is necessary to choose a pair to be deleted from the address translator.
Various replacement algorithms have been proposed, see "Cache memories, A. J. Smith, Computing Surveys, Vol. 14, No. 3, 1982".
The three most characteristic algorithms are:
LRU (Least Recently Used): this algorithm replaces the element which has remained unused for the longest time.
FIFO (First In First out): this algorithm replaces the element which has been present for the longest time.
Random: this algorithm replaces an element at random.
Comparing the algorithms with each other by determining a failure rate, i.e. the rate of addresses called by the processor which are not found in the memory level in question has proven that in most cases the LRU algorithm gives the best performance.
Generally, a buffer memory contains both instructions and numerical data. The term "information" will here be used to denote indiscriminately two types of information, that is either "instruction" or "data". The content of the buffer memory, as expressed in the fractional attribution of its capacity to data versus instruction, changes in the course of time according to the replacement algorithm which takes account of the addresses presented on the input, but does not generally take account of the type of information used. Because of this, optimum performance is not obtained and the percentage of accesses to the memory resulting in a miss is rather high. This result can be explained as follows: many programs in execution, result in most accesses to the memory by the processor relating to instructions, while few of them relate to data. In such case, the data contained in the memory is too often replaced by instructions and when it is subsequently desired to use the data again they have been deleted from the memory which leads to a miss. Conversely, for certain other programs, the miss rate may be high because the memory contains much data and only few instructions.
A method for managing information in a buffer memory which distinguishes between instructions and data has been proposed in the article "Fast memory organization", P. Favre and R. Kuhne, IBM Technical Disclosure Bulletin, Vol. 21, No. 2, 1978. It consists in using a buffer memory formed from modules, some of them being allocated to instructions and the others to data with the aid of two informations buses. A module control unit determines this allocation.
But such a management method has disadvantages. In effect, in a given configuration, each section of buffer memory allocated to instructions and to data, respectively, has a fixed capacity, and each module can only receive the type of information allocated to it. Now the percentages of accesses to instructions and to data may vary greatly according to the program executed. Because of this, for most programs, the capacities allocated to the two sections are poorly adapted, which results in a miss rate which is even higher than with a single buffer memory.
In consequence, when the allocation of such a buffer memory must be changed, it is necessary to save the total information of each modified module. The duration of such operations constitutes a non-negligible drawback of this type of structure. It may be also necessary to reconfigure the routing gates. If these are many, this operation delays functioning of the buffer memory. The buffer memory according to this prior art operates by separating instructions from data but does not allow organizing the memory elements according to several classes, each class being referenced by a tag, in order to reduce the number of comparators necessary for the referencing of the stored information. The buffer memory of the prior art is thus oriented for operating in associative mode and not for an operating mode based on classes.
Furthermore, the separation of the buffer memory into two blocks with predetermined allocation gives rise to problems of coherence between the contents of the two blocks. In effect, each element of a buffer memory will contain a group of words having successive addresses. In practice, however, such a group is often found to contain both instructions and data. This means that a particular group of words may be loaded twice, first, when calling for an instruction that is then loaded into an "instruction" element and second, when calling for a data item, that is then loaded into a "data" element, before the first loading has been deleted. Now, an information item of the opposite type to the type involved in the operation in progress can thus be loaded into the section which was not allocated to it. Now, if in case of such double loading, the value of the information block must be modified, the updating must be carried out in both sections at the same time. This leads to a more complicated system than if the buffer memory were not separated into two sections. Moreover, the fact that identical information exists in both sections of the buffer memory potentially reduces its overall capacity.